The present invention relates to address searching within a cache index. In particular, the present invention relates to address searching within a cache index using a partial physical address.
Data is stored in memory according to a physical address scheme. Software programmers, however, write program code that requires the retrieval of data using a virtual or linear address scheme (referred to herein as the xe2x80x9cvirtual addressxe2x80x9d). Therefore, it becomes necessary for a system to translate a virtual address for a piece of data to a physical address before the data can be read from physical memory.
Many conventional searching techniques require that the fall physical address be translated from the virtual address of the requested data prior to initiating a search. This significantly slows down the process of actually retrieving the data from memory, especially if the data is stored in high speed cache memory. Since a physical address is necessary before identifying and/or retrieving data from a cache, many conventional cache systems must wait until the translation from the virtual to the physical address is complete. This process can delay a search by a clock cycle or more.
In an attempt to solve this problem, other known cache systems have implemented a technique for searching an index for cache data based upon a partial physical address. This technique is based upon the recognition that a virtual address and a physical address share some address bits in common, so that these bits are available to the system immediately.
Generally, caches and cache indexes are organized into a number of sets, with each set containing one or more entry locations, or ways. In order to begin a partial-address search using the above-mentioned techniques, the available string of bits (i.e. those bits common to the virtual and physical address) must be of sufficient length to uniquely identify the individual set which might contain the requested data. According to known systems, only then may the system read out an individual set whose ways may be later searched to determine the location of requested data.
For example, for some systems, address bits 0-11 for a virtual and physical address are the same. In this example, bits 0-6 are used for addressing data within each entry of the cache, and therefore are not used to index the entries themselves.
For smaller caches, for example 16 kilobyte caches, it is possible to begin searching a cache index using bits 7-11 as many such caches are organized into 32 or fewer sets. This is possible because bits 7-11 can identify 32 individual sets (the five bits forming 25, or 32, unique binary numerals). Thus for caches with 32 or fewer sets, if bits 7-11 are available they may be immediately used to uniquely identify the individual set which might contain the requested data.
Larger caches, however, for example 256 kilobyte caches, typically contain more than 32 sets. A 256 kilobyte cache containing, for example, 256 sets requires an 8-bit string (e.g. bits 7-14) to effectively begin a search of the cache index. Known cache systems, therefore, have not initiated a search of a cache index for large caches using bits 0-11, since these systems require bits 12-14 to initiate the search anyway. These systems must wait until the translation process is complete, and the full physical address is available, before initiating a search of the cache index. The problem with this method, however, is that one or more clock cycles are wasted waiting for the translation process to finish prior to beginning the search for cache data.
The method for searching a cache index includes the steps of receiving a virtual address of a requested data element which has at least one common bit which is untranslated between the virtual address and a physical address and searching the cache index using the at least one common bit, before the virtual address is completely translated, to identify a selected block. The cache index may be organized into blocks, each block containing a plurality of sets. Each of the plurality of sets may contain at least one way, each of the ways containing an address tag.
An embodiment of a device according to the present invention includes a cache index organized into a number of sets and ways, and an auxiliary memory structure for receiving and storing intermediate search results.